package me.zk.practice1.s;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangkai
 * @date 2023/7/31 13:43
 */
public class LS438 {
    List<Character> need = new ArrayList<>();
    public  List<Integer> findAnagrams(String s, String p) {

        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length()) {
            return res;
        }
        //记录所需的字符

        for (int i = 0; i < p.length(); i++) {
            need.add(p.charAt(i));
        }

        //
        int l = 0;
        int r = p.length();
        while (r<s.length()) {
            String str = s.substring(l,r);
            if (check(str)) {
                res.add(l);
            }
            l++;
            r++;

        }

        return res;
    }
    public boolean check(String s) {
        int size = 0;
        for (int i = 0; i < s.length(); i++) {
            if (need.contains(s.charAt(i))) {
                size++;
            }
        }
        return size == s.length();
    }

    public static void main(String[] args) {
        new LS438().findAnagrams2("cbaebabacd","abc");
    }

    public List<Integer> findAnagrams2(String s, String p) {
        int[] cnt = new int[128];
        for (char c : p.toCharArray()) cnt[c]++;
        int lo = 0, hi = 0;
        List<Integer> res = new ArrayList<>();
        while (hi < s.length()) {
            if (cnt[s.charAt(hi)] > 0) {
                cnt[s.charAt(hi++)]--;
                if (hi - lo == p.length()) res.add(lo);
            } else {
                cnt[s.charAt(lo++)]++;
            }
        }
        return res;
    }
}
